import java.util.Comparator;
import java.util.PriorityQueue;


//使用大根堆用这个比较器
class IntCmp implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}


public class Test {

    //找前k个最小的数
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr == null || k<=0){
            return ret;
        }
        PriorityQueue<Integer> priorityQueue =
                new PriorityQueue<>(new IntCmp()); //此时默认使用大根堆

        for(int i =0;i<k;i++){
            priorityQueue.offer(arr[i]);
        }

        //找前k个最小的
        for(int i=k;i<arr.length;i++){
            int top = priorityQueue.peek();
            if (arr[i]<top){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        for(int i = 0;i<k;i++){
            ret[i] = priorityQueue.poll();
        }


        return ret;

    }


    //找前k个最大的元素
    public int[] biglestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (arr == null || k<=0){
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for(int i =0;i<k;i++){
            priorityQueue.offer(arr[i]);
        }
        for(int i=k;i<arr.length;i++){
            int top = priorityQueue.peek();
            if (arr[i]>top){
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        for(int i = 0;i<k;i++){
            ret[i] = priorityQueue.poll();
        }


        return ret;

    }

//    public int[] smallestK(int[] arr, int k) {
//        int[] ret = new int[k];
//        if (arr == null || k<=0){
//            return ret;
//        }
//
//        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(arr.length);
//        for(int i =0;i<arr.length;i++){
//            priorityQueue.offer(arr[i]);
//        }
//        for(int i=0;i<k;i++){
//            ret[i] = priorityQueue.poll();
//        }
//
//        return ret;
//
//    }

    public static void main3(String[] args) {

        //默认是小根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(10);
        priorityQueue.offer(1);
        priorityQueue.offer(8);
        priorityQueue.offer(7);
        priorityQueue.offer(16);
        priorityQueue.poll();
        System.out.println();
        priorityQueue.hashCode();
        System.out.println();



    }




    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        testHeap.initHeap(array);
        testHeap.createHeap();
//        testHeap.offer(80);
        System.out.println();
       testHeap.heapSort();
        System.out.println();
    }
}
